#include <vector>
#include <map>
#include <queue>

using namespace std;


/**
 * @brief 239. 滑动窗口最大值
 * https://leetcode.cn/problems/sliding-window-maximum/
 */
class Solution {
public:
    // 【方法一】使用有序 map 获取最大键
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        map<int, int> table;
        int i = 0;
        while (i < k) {
            table[nums[i++]]++;
        }

        auto getMax = [&table]() {  // O(logk)
            return table.rbegin()->first;
        };

        vector<int> res(n-k+1);
        res[0] = getMax();

        while (i < n) {
            table[nums[i-k]]--;  // erase the front element
            if (table[nums[i-k]] == 0) table.erase(nums[i-k]);
            table[nums[i]]++;
            res[i-k+1] = getMax();
            i++;
        }

        return res;
    }

private:
    using int_pair = pair<int, int>;

    static bool cmp(const int_pair& p1, const int_pair& p2) {
        return p1.first < p2.first;
    }

public:
    // 【方法二】优先队列实现
    vector<int> maxSlidingWindow2(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<int_pair, vector<int_pair>, decltype(&cmp)> pq(cmp);

        for (int i=0; i<k; i++) pq.push({nums[i], i});

        vector<int> res(n-k+1);
        for (int i = k-1; i<n; i++) {
            if (i > k-1) pq.push({nums[i], i});
            while (pq.top().second < i-k+1) {
                pq.pop();
            }
            res[i-k+1] = pq.top().first;

        }

        return res;
    }

    // 【方法三】单调队列实现
    // 有 i<j，若 i 在窗口中，则 j 必然在窗口中；
    // 如果 nums[i] <= nums[j]，则 nums[i] 不可能是滑动窗口的最大值，说明可以把
    // i 剔除了；因此队列中的元素应满足 nums[i] > nums[j]，所以为单调递减队列！
    vector<int> maxSlidingWindow3(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> dq;

        for (int i=0; i<k; i++) {
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }
            dq.push_back(i);
        }

        vector<int> res = {nums[dq.front()]};
        for (int i=k; i<n; i++) {
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);
            while (dq.front() <= i-k) dq.pop_front();
            res.push_back(nums[dq.front()]);
        }

        return res;
    }
};
